package Demo_work;

import java.util.*;

class TreeNode2 {
    int val;
    TreeNode2 left;
    TreeNode2 right;
}
public class test2 {
    public void normal_levelOrder(TreeNode2 root) {
        if(root == null) {
            return ;
        }
        Queue<TreeNode2> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode2 cur = queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    public List<List<Integer>> levelOrder(TreeNode2 root) {
        //类似用二维数组的方法来做 把值存储然后返回
        List<List<Integer>> flaglist = new LinkedList<>();
        //如果root为空 就返回一个空的链表
        if(root == null) {
            return flaglist;
        }
        Queue<TreeNode2> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            //计算队列里面有几个元素 每一次循环全部放进一个list中
            //然后每一次循环结束将list添加到retlist中 实现构建
            int size = queue.size();
            List<Integer> list = new LinkedList<>();
            while(size != 0) {
                TreeNode2 tmp = queue.poll();
                list.add(tmp.val);
                size --;

                if(tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if(tmp.right != null) {
                    queue.offer(tmp.right);
                }
            }

            flaglist.add(list);
        }
        List<List<Integer>> retlist = new LinkedList<>();
        int size = flaglist.size();
        while(size >= 0) {
            List<Integer> tmp = flaglist.get(size--);
            retlist.add(tmp);
        }
        return retlist;
    }





    //先写一个普通的层序遍历
    public static void levelorder(TreeNode2 root) {
        if(root == null) {
            return ;
        }
        //使用队列 因为先进先出
        Queue<TreeNode2> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode2 cur = queue.poll();
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
            System.out.print(cur.val+" ");
        }
    }
    public List<List<Integer>> levelOrder2(TreeNode2 root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        Queue<TreeNode2> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            while(size != 0) {
                TreeNode2 cur = queue.poll();
                tmp.add(cur.val);
                size--;

                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }
    public boolean isCompleteTree(TreeNode2 root) {
        Queue<TreeNode2> queue = new LinkedList<>();
        if(root == null) {
            return true;
        }
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode2 cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        while(!queue.isEmpty()) {
            TreeNode2 cur = queue.poll();
            if(cur != null) {
                return false;
            }
        }
        return true;
    }

    public TreeNode2 lowestCommonAncestor(TreeNode2 root, TreeNode2 p, TreeNode2 q) {
        TreeNode2 cur  = root;
        if(root == null) {
            return root;
        }
        //情况1：p或者q就是 root
        if(p == root || q == root) {
            return root;
        }
        //情况2：p q 在root的一边
        TreeNode2 left = lowestCommonAncestor(root.left,p,q);
        TreeNode2 right = lowestCommonAncestor(root.right,p,q);
        if(left != null && right != null) {
            return root;
        }
        //情况2：p q 在root的两边
        if(left != null) {
            return left;
        } else {
            return right;
        }
    }
    public boolean getPath(TreeNode2 root, TreeNode2 node, Stack<TreeNode2> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flgLeft = getPath(root.left,node,stack);
        if(flgLeft) {
            return true;
        }
        boolean flgRight = getPath(root.right,node,stack);
        if(flgRight) {
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode2 lowestCommonAncestor2(TreeNode2 root, TreeNode2 p, TreeNode2 q) {
        if(root == null) {
            return null;
        }
        Stack<TreeNode2> stackLeft = new Stack<>();
        Stack<TreeNode2> stackRight = new Stack<>();
        int size = Math.abs(stackLeft.size() - stackRight.size());
        if(stackLeft.size() > stackRight.size()) {
            while(size != 0) {
                size--;
                stackLeft.pop();
            }
        } else {
            while(size != 0) {
                size--;
                stackRight.pop();
            }
        }
        while(stackLeft.size() != 0 && stackRight.size() != 0) {
            TreeNode2 left = stackLeft.pop();
            TreeNode2 right = stackRight.pop();
            if(left == right) {
                return left;
            }
        }
        return null;
    }
    public static void main(String[] args) {

    }
}
